#[test]
fn test_trap() {
    assert_eq!(trap(vec![0,1,0,2,1,0,1,3,2,1,2,1]), 6);
    assert_eq!(trap(vec![4,2,0,3,2,5]), 9);
    assert_eq!(trap(vec![]), 0);
}

/*
    42. 接雨水
    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

    示例 1：
    输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

    示例 2：
    输入：height = [4,2,0,3,2,5]
    输出：9

    提示：
    n == height.length
    0 <= n <= 3 * 104
    0 <= height[i] <= 105
 */
pub fn trap(height: Vec<i32>) -> i32 {
    if height.is_empty() {
        return 0;
    }
    
    let (mut left, mut right, mut ans) = (0, height.len() - 1, 0);
    let (mut left_max, mut right_max) = (0, 0);
    while left < right {
        left_max = left_max.max(height[left]);
        right_max = right_max.max(height[right]);
        if height[left] < height[right] {
            ans += left_max - height[left];
            left += 1;
        } else {
            ans += right_max - height[right];
            right -= 1;
        }
    }
    ans
}